package nowcoder;
/**
 * 23271-数组中出现次数超过一半的数字
 * https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 */
import java.util.*;
public class Day03_2 {
    // 要求：空间复杂度O(1), 时间复杂度O(n)
    // [1,2,3,2,2,2,5,4,2]
    // 2
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        int count = 1;
        for(int i = 1; i < array.length; i ++){
            if(array[i] == array[i-1]){
                count ++;
            }else{
                count = 1;
            }
            if(count > array.length/2){
                return array[i];
            }
        }
        return array[0];
    }
}
